package pers.study.datastructure.hash;

import java.util.TreeMap;

/**
 * @author rookie
 * @version 1.0
 * @date 2020/4/25 9:01
 */
public class HashTable<K, V> {


    /**利用素数表进行动态扩容*/
    private final int[] capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private  int capacityIndex = 10;

    private TreeMap<K, V>[] hashTable;
    private int M;
    private int size;

    public HashTable(int M){
        this.M = M;
        size = 0;
        hashTable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }
    public HashTable(){
        this(97);
    }

    private int hash(K key){
        return (key.hashCode() & 0x7fffffff) % M;
    }
    public int size(){
        return size;
    }
    public void  add(K key, V value){
        TreeMap<K, V> map = hashTable[hash(key)];
        if (map.containsKey(key)){
            map.put(key,value);
        }
        else {
            map.put(key, value);
            size ++;
            if (size >= upperTol * M && (capacityIndex + 1) < capacity.length){
                capacityIndex ++;
               resize( capacity[capacityIndex]);
            }
        }
    }

    private void resize(int newM){
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for(int i = 0 ; i < newM ; i ++) {
            newHashTable[i] = new TreeMap<>();
        }

        int oldM = M;
        this.M = newM;
        for(int i = 0 ; i < oldM ; i ++){
            TreeMap<K, V> map = hashTable[i];
            for(K key: map.keySet()) {
                newHashTable[hash(key)].put(key, map.get(key));
            }
        }

        this.hashTable = newHashTable;
    }

    public V remove(K key){
        TreeMap<K, V> map = hashTable[hash(key)];
        V ret = null;
        if (map.containsKey(key)){
            ret = map.remove(key);
            size --;
            if (size < lowerTol * M && capacityIndex - 1 >= 0 ){
                capacityIndex --;
                resize(capacity[capacityIndex]);
            }
        }
        return ret;
    }
    public void set(K key, V value){
        TreeMap<K, V> map = hashTable[hash(key)];
        if (!map.containsKey(key)){
            throw new IllegalArgumentException(key + "error");
        }
        map.put(key, value);
     }
     public boolean contains(K key){
        return hashTable[hash(key)].containsKey(key);
     }
     public V get(K key){
        return hashTable[hash(key)].get(key);
     }
}

